//
//  CodeQues.swift
//  SFQuestion
//
//  Created by sr liu on 2021/7/14.
//


//  一些博客算法的学习


import Foundation
//王争 数据结构 具体看讲义
/*
 
 贪心：一条路走到黑，就一次机会，只能哪边看着顺眼走哪边
 回溯：一条路走到黑，无数次重来的机会，还怕我走不出来 (Snapshot View)
 动态规划：拥有上帝视角，手握无数平行宇宙的历史存档， 同时发展出无数个未来 (Versioned Archive View)
 
 */
//动态规划
class DP {
    //背包问题
    let n = 5//物品个数
    let w = 9//背包承受的最大重量
    let weight = [2,2,4,6,3]//物品重量
    var maxW = 0//存放最大结果
    
    func testDp() {
        self.knapsack1(n, w, weight)
    }
    
    //MARK:通过递归回溯
    //f(i,cw) 函数，i表示将要决策第几个物品是否装入背包，cw表示当前背包中物品的总重量
    func f(seq i: Int, currentWeight cw: Int) {
        if i == n || cw == w {
            if cw > maxW {
                maxW = cw//我理解这里就是把当前🎒的重量记下来
            }
            return
        }
        
        //递归决策下面的分支
        //一个是假定当前🎒没装第i个，那么决策下一个的时候，自然还是传入的cw
        f(seq: i + 1, currentWeight: cw)
        if cw + weight[i] <= w {
            f(seq: i + 1, currentWeight: cw + weight[i])
        }
    }
    
    //为了避免重复计算，可以记录下哪个已经决策过了
    //用一个二维数组来匹配并标记 i和cw的状态，其实可以想别的办法，比如两者按规则组合放到dic中
    var mem: [[Bool]] = {
        var nums = [[Bool]]()
        for _ in 0..<5 {
            var columns = [Bool]()
            for _ in 0...10 {
                columns.append(false)
            }
            nums.append(columns)
        }
        print("--mem---")
        return nums
    }()
    //var cookies = [[Int]](repeating: [Int](repeating: 0, count: 7), count: 9)
    
    //MARK:递归回溯优化
    func f1(seq i: Int, currentWeight cw: Int) {
        if i == n || cw == w {
            if cw > maxW {
                maxW = cw//我理解这里就是把当前🎒的重量记下来
            }
            return
        }
        
        if self.mem[i][cw] {return}
        self.mem[i][cw] = true
        f(seq: i + 1, currentWeight: cw)
        if cw + weight[i] <= w {
            f(seq: i + 1, currentWeight: cw + weight[i])
        }
    }
    
    //MARK:使用动态规划的思想来做
    func knapsack(_ n: Int, _ w: Int, _ weight: [Int]) -> Int {
        //利用二维数组记录每一行的状态 申请w+1因为 不装为0是一种状态装满就是w,方便数组的操作
        var states = [[Int]](repeating: [Int](repeating: 0, count: w + 1), count: n)
        //从0开始
        states[0][0] = 1;//检测第一个不放入的情况 背包总重量是0
        //放入的话
        if weight[0] <= w {
            states[0][weight[0]] = 1
        }
        //以第一行决策为基础开始遍历
        for i in 1..<n {
            //第i个物品不放入背包
            for j in 0...w {//从上一行的状态拷贝到下一行,不知道上一行到哪里，所以遍历到头
                if states[i-1][j] == 1 {
                    states[i][j] = 1
                }
            }
            for j in 0...w-weight[i] {//j就是0到背包总重量，j加上要放入的重量超过w就没用了
                if states[i-1][j] == 1 {
                    states[i][(j + weight[i])] = 1
                }
            }
            //最后从最底下倒着找1
            for i in (0...w).reversed() {
                if states[n-1][i] == 1 {
                    return i
                }
            }
        }
        return 0
    }
    
    //MARK:使用动态规划的思想来做，只用一维数组
    func knapsack1(_ n: Int, _ w: Int, _ weight: [Int]) -> Int {
        var states = [Int].init(repeating: 0, count: w+1)
        states[0] = 0
        if weight[0] <= w {
            states[0] = 1
        }
        for i in 0..<n {
            for j in (0...w-weight[i]).reversed() {
                if states[j] == 1 {
                    states[j + weight[i]] = 1
                }
            }
        }
        for i in (0...w).reversed() {
            if states[i] == 1 {
                return i
            }
        }
        
        return 0
    }
    
    //MARK:0-1 背包问题升级版
    
    //MARK:钱币 凑出金额
    /*
     https://www.zhihu.com/question/23995189/answer/613096905
     dp：能将大问题拆成几个小问题，且满足无后效性、最优子结构性质
     
     
     面值为1、5、11元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票
     假如w是15
     
     f(n)代表凑出n需要的张数
     那么这里的f（n）之和 f(n-1) f(n-5) f(n-11)相关.
     f(n) = min{f(n-1), f(n-5), f(n-11)} + 1
     比如f（15） 15元，如果最后一张是1元 那么只要考虑 f(14) 加上1即可
                    如果最后一张是5元 那么只要考虑 f(10) 加上1即可
                    如果最后一张是10元 那么只要考虑 f(5) 加上1即可
     */
    func money(_ n: Int) -> Int {
        var moneyCount = Array.init(repeating: 0, count: Int(n + 1))
        var cost: Int = NSIntegerMax
        for i in 1...n {
            cost = NSIntegerMax
            if i >= 1 {
                cost = min(cost, moneyCount[i-1] + 1)
            }
            if i >= 5 {//等于号 就是他自己一张就够了
                cost = min(cost, moneyCount[i-5] + 1)
            }
            if i >= 11 {
                cost = min(cost, moneyCount[i-11] + 1)
            }
            moneyCount[i] = cost
        }
        print(moneyCount)
        return min(moneyCount[n-1], moneyCount[n-5], moneyCount[n-11]) + 1
    }
    
    
}
